The present invention relates to a simple decoding method and a simple decoder circuit therefor which permit easy decoding of convolutional codes, but do not have error correcting capability by themselves, and which will hereinafter be called a simple decoding method and simple decoder, respectively.
Of presently known convolutional code decoding methods, a decoding algorithm proposed by A. J. Viterbi is regarded as a highly reliable decoding method with the highest error-correction capability and it has already been put into practical use as a Viterbi decoder in a limited field of satellite communications, proving its superiority over the prior art. The Viterbi decoder has excellent properties as mentioned above, but it is defective in that the circuit scale becomes very large to enhance the error correcting rate, resulting in an increase in power dissipation.
On the other hand, threshold decoding and sequential decoding have been proposed as error-correcting-and-decoding methods for convolutional codes. These decoding methods also call for large-scale circuitry, not as large as in the case of the Viterbi decoder, but still power dissipation is inevitably large. In view of such disadvantages of the prior art, an SST (Scarce State Transition) scheme has been proposed and put into practical use as a system which permits reduction of the power dissipation and circuit scale of the Viterbi decoder (Ishitani et al, "A Scarce-State-Transition Viterbi-Decoder VLSI for Error Correction", IEEE JOURNAL OF SOLID-STATE CIRCUITS, VOL. SC-22, No. 4, AUGUST 1987, pp 575-581).
FIG. 1 shows an example of an SST Viterbi decoder with a constraint length K=7 and a coding rate R=1/2, constructed through application of the SST scheme to a conventional Viterbi decoding circuit in a narrow sense which comprises branch metric circuits, ACS (Add-Compare-Select) circuits and path memory circuits as shown in the above-mentioned literature. In the SST Viterbi decoder, received convolutional codes X.sub.1 and X.sub.2 provided to terminals 11.sub.1 and 11.sub.2, which may include errors in the transmission channel, are decoded by a simple decoder 2 having no error-correcting capability to obtain estimated decoded data D' of original data D. The simple decoder shown in the literature and referred to as a pre-decoder is one that decodes one bit of the original data by a modulo-2 addition of code data from seven shift stages which are specified by a coupling vector (1110111010) and selected from 10-bit code data held in 10 shift stages. Then, the estimated decoded data D' is re-encoded by an encoder 3 of the same construction as that of a convolutional encoder at the transmitting side, and the re-encoded convolutional codes X.sub.1 ' and X.sub.2 ' are compared by comparators (exclusive-OR circuits) 13.sub.1 and 13.sub.2 with the received convolutional code data (soft decision data) X.sub.1 and X.sub.2, respectively.
If there are no errors in the transmission channel, the received code data X.sub.1 and X.sub.2 and the re-encoded data X.sub.1 ' and X.sub.2 ' match each other and the outputs from the comparators 13.sub.1 and 13.sub.2 both go to "0's." The convolutional code data X.sub.1 and X.sub.2 normally influence each other over a plurality of bits preceding and following them as the result of convolution of the original data, and therefore, when a channel error occurs, an abnormal bit pattern is produced which would be impossible with correct convolutional codes. On the other hand, regarding the output re-encoded data from the convolutional encoder 3, even if the input data D' includes an estimation error, no abnormal bit pattern will be introduced into the encoded data as the convolutional codes. Hence, when a channel error occurs, the comparators 13.sub.1 and 13.sub.2 provide "1's" continuously or discontinuously over a plurality of bits. The compared outputs representative of such an estimation error are provided to a conventional (i.e., narrow sense) Viterbi decoder 14 for decoding the estimation error. The decoded output from the narrow sense Viterbi decoder 14 and the decoded output D' from the simple decoder 2 are subjected to a modulo-2 addition by a modulo-2 addition circuit 15, thereby correcting the estimation error in the decoded output D' to obtain the original data D. Delay circuits 12.sub.1, 12.sub.2 and 16 are provided to time the data.
With such an SST Viterbi decoder, when no error is induced in the convolutionally encoded data in the transmission channel, the input to the narrow-sense Viterbi decoder 14 is always a "0." Therefore, the Viterbi decoder 14 processes only a code error. That is, data that is stored in the path memory circuits in the narrow-sense Viterbi decoder 14 is all "0" except when an error is induced in the transmitted signal, and the ON-OFF switching operation of gates rarely occurs in the path memory circuits. Since a CMOS circuit usually dissipates power by the ON-OFF switching of signals, power dissipation of the SST Viterbi decoder is far less than that of the conventional Viterbi decoder (about 40% when the bit error rate after Viterbi decoding, Pe, is 10). Moreover, the conventional Viterbi decoder employs a maximum likelihood decision circuit to reduce a required path memory length, but the Viterbi decoder utilizing the SST scheme permits reduction of the path memory length, and hence enables the omission of the maximum likelihood decision circuit. For these reasons, the SST Viterbi decoder affords reduction of the power dissipation and circuit scale or hardware size of the conventional Viterbi decoder 14.
FIG. 2 shows an example of the simplest construction of a convolutional encoder with coding rate R=1/2 and constraint length K=4 which is used at the transmission side in the prior art. In this example, the encoder is composed of a three-stage shift register 4 and modulo-2 addition circuits 5.sub.1 and 5.sub.2. The original data D (D.sub.1, D.sub.2, . . . ) are sequentially input into the shift register 4 via an input terminal 6 and the modulo-2 addition circuit 5.sub.1 performs modulo-2 addition of the outputs from all shift stages of the shift register 4, whereas the modulo-2 addition circuit 5.sub.2 performs modulo-2 addition of the outputs from first and third shift stages of the shift register 4. The modulo-2 addition circuits 5.sub.1 and 5.sub.2 output convolutionally encoded data X.sub.1 and X.sub.2 to terminals 7.sub.1 and 7.sub.2. The SST Viterbi decoder at the reception side, shown in FIG. 1, receives and decodes the encoded data X.sub.1 and X.sub.2. In the encoder of FIG. 2, since the outputs from the first and third stages of the shift register 4 are always provided to both modulo-2 addition circuits 5.sub.1 and 5.sub.2, the logical relationship of the data X.sub.1 relative to the data X.sub.2 is equivalent to that in the case where the data X.sub.2 is set to a "0" and the output from the second shift stage is assumed to be the data X.sub.1. It can readily be understood, therefore, that the simple decoder 2 in FIG. 1, which is the counterpart of the encoder in FIG. 2, can be formed by one modulo-2 addition circuit as depicted in FIG. 3. In this instance, the coupling vector which couples the input code data to the modulo-2 addition circuit is represented by (11).
It is desired, in general, that the coding rate R=n/m (where n is the number of input information bits and m is the number of output bits) be raised, that is, made closer to 1 so as to enhance the code transmission efficiency, and that the constraint length K be increased to improve the error-correcting capability. The simple decoder 2 that is needed in the SST Viterbi decoder can be implemented relatively easily when the coding rate R is 1/2 and the constraint length K is 7 or below, as referred to in the above-mentioned literature, but no logic design algorithm has been proposed for a simple decoder with an arbitrary coding rate R which is usually expressed by n/m. In fact, there are not available any simple decoders with coding rates R other than 1/2, except that the inventors of this application happened to succeed in implementing only a simple decoder with a coding rate R=3/4 and constraint length K=7 after repeated trial and error (Kawazoe et al, "SST Type Viterbi Decoder for High Rate Convolutional Codes", Institute of Electronics and Communication Engineers of Japan, 1991 Autumn Convention, B-156). Thus it is difficult, with the prior art, to construct simple decoders for convolutional codes of arbitrary coding rates R other than those whose constraint lengths are 7 or shorter and whose coding rates are 1/2 and, therefore, it is difficult, in general, to construct the SST type Viterbi decoder which involves the use of such a simple decoder. On this account, decoding of codes with a coding rate R=n/m inevitably calls for the conventional Viterbi decoder which is not the SST type, and hence still suffers the aforementioned defect of large power dissipation.